/*
 * nfa.h
 *
 *  Created on: 2009-8-29
 *      Author: toxic
 */

#ifndef NFA_H_
#define NFA_H_

#include <set>
#include <vector>
#include "toxic.h"

BEGIN_NAMESPACE_TOXIC

using std::set;
using std::vector;

class Edge;
class Charset;

class State {
public:
	State();
	~State();

	static void connect(State* from, State* to, Charset* chars);

	static int count() {
		return s_id_ - 1;
	}

public:
	Edge* e1;
	Edge* e2;
	int id;
	int refCount;

private:
	static int s_id_;
};


class Edge {
public:
	Edge(State* next_, Charset* chars_);
	~Edge();

public:
	State* next;
	Charset* chars;
	bool visited;
};


class NfaSegment {
public:
	NfaSegment()
	:start(0)
	,accept(0) {

	}

	NfaSegment(State* start_, State* accept_)
	:start(start_)
	,accept(accept_) {

	}

	~NfaSegment() {

	}

	bool empty() const {
		return start == 0 && accept == 0;
	}

	static NfaSegment concatenation(NfaSegment r, NfaSegment s);
	static NfaSegment alternation(NfaSegment r, NfaSegment s);
	static NfaSegment zeroOrMoreRepetition(NfaSegment r);
	static NfaSegment oneOrMoreRepetition(NfaSegment r);
	static NfaSegment option(NfaSegment r);

public:
	State* start;
	State* accept;
};


class Nfa {
	typedef set<State*> state_set_t;
public:
	Nfa(NfaSegment nfa)
	:nfa_(nfa) {
		epsilonClosure_.reserve(State::count() + 1);
		epsilonClosure_.resize(State::count() + 1);
	}

	~Nfa() {
		destroy(nfa_.start);
	}

	bool empty() const {
		return nfa_.empty();
	}

	void print() const {
		print(nfa_.start);
	}

	void printEpsilonClosure();
	void printEpsilonClosure(int id);

private:
	state_set_t* epsilonClosure(State* state);
	state_set_t* constructEpsilonClosure(State* state);
	state_set_t* constructEpsilonClosureImplement(State* state, vector<bool*>& edgeVisitInfo);

private:
	static void print(State* state);
	static void destroy(State* state);

private:
	NfaSegment nfa_;
	vector<state_set_t*> epsilonClosure_;
};


bool regexInfixToPostfix(const string& infix, string& postfix);
Nfa* regexToNfa(const string& regex);

END_NAMESPACE_TOXIC

#endif /* NFA_H_ */
